package com.leetcode.sort;

public class Quick {

    public void sort(int[] array , int left , int right) {
        if(left > right) {
            return;
        }
        for (int l = 0 ; l < array.length ; l++) {
            System.out.print(array[l] + " ");
        }
        System.out.println();
        // base中存放基准数 默认去左边第一个
        int base = array[left];
        //copy left right 做探索变量 因为left right 后面要用来迭代
        int i = left, j = right;
        while(i != j) {
            // 顺序很重要，先从右边开始往左找，直到找到比base值小的数
            while(array[j] >= base && i < j) {
                j--;
            }

            // 再从左往右边找，直到找到比base值大的数
            while(array[i] <= base && i < j) {
                i++;
            }

            // 上面的循环结束表示找到了位置或者(i>=j)了，交换两个数在数组中的位置
            if(i < j) {
                int tmp = array[i];
                array[i] = array[j];
                array[j] = tmp;
            }
        }

        // 将基准数放到中间的位置（基准数归位）
        array[left] = array[i];
        array[i] = base;

        // 递归，继续向基准的左右两边执行和上面同样的操作
        // i的索引处为上面已确定好的基准值的位置，无需再处理
        sort(array, left, i - 1);
        sort(array, i + 1, right);
    }

    public static void main(String[] args) {
        Quick quick = new Quick();
        int[] unsort = {72,6,57,88,60,42,83,73,48,85};
        quick.sort(unsort, 0 , unsort.length - 1);
    }
}
